package com.fjl.array.leetcode977;

import java.util.Arrays;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/13 14:52
 */
/*
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
    输入：nums = [-4,-1,0,3,10]
    输出：[0,1,9,16,100]
    解释：平方后，数组变为 [16,1,0,9,100]
    排序后，数组变为 [0,1,9,16,100]
示例 2：
    输入：nums = [-7,-3,2,3,11]
    输出：[4,9,9,49,121]
提示：
    1 <= nums.length <= 104
    -104 <= nums[i] <= 104
    nums 已按 非递减顺序 排序
进阶：请你设计时间复杂度为 O(n) 的算法解决本问题
 */
public class Clazz {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        // 两个指针分别初始化在正负子数组绝对值最大的元素索引
        int i = 0, j = n - 1;
        // 得到的有序结果是降序的
        int p = n - 1;
        int[] res = new int[n];
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                res[p] = nums[i] * nums[i];
                i++;
            } else {
                res[p] = nums[j] * nums[j];
                j--;
            }
            p--;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] sortedSquares = new Clazz().sortedSquares(new int[]{-5,-3,-2,-1});
        System.out.println(Arrays.toString(sortedSquares));
    }
}
